package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/cousins-in-binary-tree/">二叉树的堂兄弟节点(Cousins in Binary Tree)</a>
 * <p>在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。</p>
 * <p>如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。</p>
 * <p>我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。</p>
 * <p>只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,2,3,4], x = 4, y = 3
 *                      1
 *                     / \
 *                    2   3
 *                   /
 *                  4
 *      输出：false
 *
 * 示例 2：
 *      输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
 *      输出：true
 *
 * 示例 3：
 *      输入：root = [1,2,3,null,4], x = 2, y = 3
 *      输出：false
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>给定树的节点数范围是 [1, 100]。</li>
 *     <li>每个节点的值都是整数，范围为 [0, 99] 。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0993CousinsInBinaryTree_S
 * @see LC2641CousinsInBinaryTree_II_M
 * @since 2023/11/17 17:20
 */
public class LC0993CousinsInBinaryTree_S {

    static class Solution {

        public boolean isCousins(TreeNode root, int x, int y) {
            if (root == null || root.val == x || root.val == y) {
                return false;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            // xValueNode：值 x 对应的节点；xValueParentNode：值 x 对应的节点的父节点
            TreeNode xValueNode = null;
            TreeNode xValueParentNode = null;
            // yValueNode：值 y 对应的节点；yValueParentNode：值 y 对应的节点的父节点
            TreeNode yValueNode = null;
            TreeNode yValueParentNode = null;
            while (!queue.isEmpty()) {
                int currLevelNodeSize = queue.size();
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = queue.poll();
                    if (currNode.left != null) {
                        queue.add(currNode.left);
                        // 找节点
                        if (currNode.left.val == x) {
                            xValueNode = currNode.left;
                            xValueParentNode = currNode;
                        }
                        if (currNode.left.val == y) {
                            yValueNode = currNode.left;
                            yValueParentNode = currNode;
                        }
                    }
                    if (currNode.right != null) {
                        queue.add(currNode.right);
                        // 找节点
                        if (currNode.right.val == x) {
                            xValueNode = currNode.right;
                            xValueParentNode = currNode;
                        }
                        if (currNode.right.val == y) {
                            yValueNode = currNode.right;
                            yValueParentNode = currNode;
                        }
                    }
                }

                if (xValueNode != null && yValueNode != null) {
                    // 两个节点都找到了，那么判断它们是不是堂兄弟节点：
                    //      1.如果父亲结点不相等，说明是堂兄弟结点；
                    //      2.如果父亲节点相等，说明说兄弟节点，而非堂兄弟节点
                    return xValueParentNode != yValueParentNode;
                } else if (xValueNode != null || yValueNode != null) {
                    // 一个节点找到了，一个节点没找到，非堂兄弟节点
                    return false;
                }
                //else {
                //    // 当前层所有节点遍历完以后：两个节点都没找到，什么也不做
                //}
            }
            return false;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.left = new TreeNode(4);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);
        root2.left.right = new TreeNode(4);
        root2.right.right = new TreeNode(5);

        Solution solution = new Solution();
        System.out.println(solution.isCousins(root1, 4, 3));
        System.out.println(solution.isCousins(root2, 5, 4));
    }
}
